home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 395_01 / avl / slbuild.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-27  |  3.3 KB  |  114 lines
  1. /* implementation file for build from sorted sequence
  2.    function for sorted list data structure. */
  3.  
  4. #include <string.h>
  5.  
  6. #include "align.h"
  7. #include "stckallc.h"
  8. #include "sortlist.h"
  9. #include "slintrnl.h"
  10.  
  11. /* macro which returns non-zero if argument is power of 2,
  12.    otherwise 0. */
  13. #define POWER_OF_2(NN) (!((NN) & ((NN) - 1)))
  14.  
  15. /* structure which groups unchanging parameters to minimize
  16.    stack usage by recursive function */
  17. typedef struct
  18.   {
  19.     /* function to get next element is sequence which must be sorted
  20.        in ascending order */
  21.     int (*next_elem)(void *elem, void *other_param);
  22.     /* the other parameter to the "next_elem" function */
  23.     void *other_param;
  24.     /* pointer to node allocation stack */
  25.     ALLOC_STACK *node_as;
  26.   }
  27. CONST_PARAM;
  28.  
  29. /* recursive function to build a tree */
  30. static SL_RESULT build_tree
  31.   (
  32.     /* pointer to pointer to set to root of tree */
  33.     void **tree,
  34.     /* number of elements in sequence */
  35.     size_t n_elems,
  36.     CONST_PARAM *param
  37.   )
  38.   {
  39.     if (n_elems == 0)
  40.       *tree = (void *) 0;
  41.     else
  42.       {
  43.     SL_RESULT r;
  44.  
  45.     if (!(*tree = get_alloc_stack(param->node_as)))
  46.       return(SL_MEM_ALLOC_FAIL);
  47.  
  48.     r = build_tree(&(NODE(*tree)->branch[LESS_BRANCH]),
  49.                (n_elems - 1) >> 1, param);
  50.  
  51.     if (r != SL_SUCCESS)
  52.       return(r);
  53.  
  54.     if ((*(param->next_elem))(ELEM_IN_NODE(*tree), param->other_param))
  55.       return(SL_ABORT);
  56.  
  57.     r = build_tree(&(NODE(*tree)->branch[GREATER_BRANCH]),
  58.                n_elems >> 1, param);
  59.  
  60.     if (r != SL_SUCCESS)
  61.       return(r);
  62.  
  63.     /* the two subtrees will have the same depth unless the
  64.            total number of elemenets is a power of 2 greater than
  65.        1 */
  66.     NODE(*tree)->balance = n_elems == 1 ? 0 :
  67.                      POWER_OF_2(n_elems) ? 1 : 0;
  68.       }
  69.     return(SL_SUCCESS);
  70.   }
  71.  
  72.  
  73. /* build a sorted list from an existing sorted sequence.  the function
  74.    returns SL_SUCCESS if successful.  returns SL_MEM_ALLOC_FAIL if
  75.    a memory allocation fails.  returns SL_ABORT if the caller-supplied
  76.    function returns a non-zero value.  returns SL_NOT_EMPTY if the
  77.    sorted list is not empty. */
  78. SL_RESULT build_sort_list
  79.   (
  80.     /* sorted list.  must be initialized but empty.  if function does
  81.        not return SL_SUCCESS, the list will remain empty. */
  82.     SORT_LIST *sl,
  83.     /* number of elements in sequence */
  84.     size_t n_elems,
  85.     /* function to get next element is sequence which must be sorted
  86.        in ascending order.  if this function returns a value other than
  87.        zero, the build operation is aborted and the sorted list is
  88.        empty.  the first parameter to the function is a pointer to
  89.        the memory buffer to place the element in.  the second parameter
  90.        is the void pointer value passed below */
  91.     int (*next_elem)(void *elem, void *other_param),
  92.     /* the other parameter to the "next_elem" function */
  93.     void *other_param
  94.   )
  95.   {
  96.     CONST_PARAM param;
  97.     SL_RESULT r;
  98.  
  99.     if (sl->tree)
  100.       return(SL_NOT_EMPTY);
  101.  
  102.     param.next_elem = next_elem;  
  103.     param.other_param = other_param;  
  104.     param.node_as = &(sl->node_alloc_stack);
  105.  
  106.     r = build_tree(&(sl->tree), n_elems, ¶m);
  107.     if (r != SL_SUCCESS)
  108.       {
  109.     sl->tree = (void *) 0;
  110.     clear_alloc_stack(&(sl->node_alloc_stack));
  111.       }
  112.     return(r);
  113.   }
  114.